package ysf.com.mediumdifficulty;

import org.apache.commons.lang3.ArrayUtils;

import java.util.Arrays;

/**
 * @author ysf
 * @date 2021/6/10 22:24
 */
public class FourthDemo {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2,3,4};
        int[] nums2 = new int[]{5,6,7,8};
       /* double result = findMedianSortedArrays(nums1, nums2);
        System.out.println(result);*/

        double results = findMedianSortedArraysf(nums1, nums2);
        System.out.println(results);

    }

    // 错误的方法
    public static double findMedianSortedArrays(int[] A,int[] B){
        int m = A.length;
        int n = B.length;
        int len = m + n;   // 合并后数组的长度
        int left = -1 , right =-1;
        int aStart = 0, bStart = 0;
        for (int i = 0; i < len / 2; i++) {
            left = right;
            if(aStart < m && (bStart >= n || A[aStart] < B[bStart])){
                right = A[aStart++];

            }else {
                right = B[bStart];
            }
        }
        if ((len & 1) == 0)
            return (left + right) /2.0;
        else
            return right;
    }

    // leetcode解法
    public static double findMedianSortedArraysf(int[] A,int[] B){
        int m = A.length;
        int n = B.length;
        if(m > n){
            return findMedianSortedArraysf(B,A);
        }
        int iMin = 0, iMax = m;

        while (iMin <= iMax){
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 -i;
            if(j != 0 && i != m && B[j-1] > A[i]){   // i 需要增大
                iMin = i + 1;
            }else if (i != 0 && j != n && A[i-1] > B[j]){
                iMax = i - 1;
            }else {
                int maxLeft = 0;
                if(i == 0){ maxLeft = B[j-1];}
                else if (j==0){maxLeft = A[i-1];}
                else {maxLeft = Math.max(A[i-1],B[j-1]);}
                if ((m+n)%2 == 1){return maxLeft;}  // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m){minRight = B[j];}
                else if (j == n){minRight = A[i];}
                else {minRight = Math.min(B[j],A[i]);}
                return (maxLeft + minRight) / 2.0;    // 如果是偶数的话返回结果
            }
        }
        return 0.0;
    }



    /**
     * 如何在数组中求中位数 result
     *  1,如果该组元素个数为偶数
     *      a, index1 = (该组元素个数 / 2)
     *      b, index2 = (index1 + 1)
     *      c, result = (index1 + index2) / 2
     *  2,如果该组元素个数为奇数
     *      a, index = (元素个数 + 1) / 2
     *      b, 得到的index值,index指定该组数据中的下标元素就是中位数
     *      c, result = Array[index]
     * personal method
     * @param A
     * @param B
     * @return
     */
    public static double getResult(int[] A,int[] B){
        //第一步将数组合并然后排序
        int[] ints = ArrayUtils.addAll(A, B);  // apache.commons.lang3.ArrayUtils包下的addAll方法合并两个数组
        //System.out.println(JSON.toJSONString(ints));
        Arrays.sort(ints);   // 数组排序
        //System.out.println(JSON.toJSONString(ints));
        // 数组的长度
        int length = ints.length;
        // 偶数
        if(length % 2 == 0) {
            int index1 = length / 2;
            int index2 = index1 + 1;
            double result = (index1 + index2) / 2;
            return result;
        }
        // 奇数
        else{
            int index = (length + 1) / 2;
            double result = ints[index];
            return result;
        }
    }


}
